<head>
    <meta charset="UTF-8">
<title>算法提高 选择排序</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>﻿</p>
<h2 style="text-align: center; margin: 13pt 0cm" align="center"><span style="font-family: 黑体; mso-ascii-font-family: Arial; mso-hansi-font-family: Arial">选择排序</span></h2>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【问题描述】</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span lang="EN-US"><span style="mso-tab-count: 1"><font face="Times New Roman">&nbsp; &nbsp; &nbsp; &nbsp;</font></span></span></font><span style="color: rgb(32, 0, 0); font-family: 'Times New Roman', 宋体; font-size: 14px; text-align: left; ">排序，顾名思义，是将若干个元素按其大小关系排出一个顺序。形式化描述如下：有n个元素a[1]，a[2]，&hellip;，a[n]，从小到大排序就是将它们排成一个新顺序a[i[1]]&lt;a[i[2]]&lt;&hellip;&lt;a[i[n]]</span></p>
<p><span style="color: rgb(32, 0, 0); font-family: 'Times New Roman', 宋体; font-size: 14px; text-align: left; ">　　i[k]为这个新顺序。</span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span lang="EN-US"><span style="mso-tab-count: 1"><font face="Times New Roman">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">选择排序的思想极其简单，每一步都把一个最小元素放到前面，如果有多个相等的最小元素，选择排位较考前的放到当前头部。还是那个例子：</span><span lang="EN-US"><font face="Times New Roman">{3 1 5 4 2}</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">：</span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第一步将</span><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">放到开头（第一个位置），也就是交换</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">1</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，即</span><span lang="EN-US"><font face="Times New Roman">swap(a[0],a[1])</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">得到</span><span lang="EN-US"><font face="Times New Roman">{1 3 5 4 2}</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第二步将</span><span lang="EN-US"><font face="Times New Roman">2</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">放到第二个位置，也就是交换</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">2</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，即</span><span lang="EN-US"><font face="Times New Roman">swap(a[1],a[4])</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">得到</span><span lang="EN-US"><font face="Times New Roman">{1 2 5 4 3}</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第三步将</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">放到第三个位置，也就是交换</span><span lang="EN-US"><font face="Times New Roman">5</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">3</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，即</span><span lang="EN-US"><font face="Times New Roman">swap(a[2],a[4])</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">得到</span><span lang="EN-US"><font face="Times New Roman">{1 2 3 4 5}</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第四步将</span><span lang="EN-US"><font face="Times New Roman">4</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">放到第四个位置，也就是交换</span><span lang="EN-US"><font face="Times New Roman">4</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">4</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，即</span><span lang="EN-US"><font face="Times New Roman">swap(a[3],a[3])</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">得到</span><span lang="EN-US"><font face="Times New Roman">{1 2 3 4 5}</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第五步将</span><span lang="EN-US"><font face="Times New Roman">5</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">放到第五个位置，也就是交换</span><span lang="EN-US"><font face="Times New Roman">5</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">5</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，即</span><span lang="EN-US"><font face="Times New Roman">swap(a[4],a[4])</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">得到</span><span lang="EN-US"><font face="Times New Roman">{1 2 3 4 5}</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">输入</span><span lang="EN-US"><font face="Times New Roman">n</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个整数，输出选择排序的全过程。</span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; font-size: medium; ">要求使用递归实现。</span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【输入格式】</font></span></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第一行一个正整数</span><span lang="EN-US"><font face="Times New Roman">n</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">，表示元素个数</span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">第二行为</span><span lang="EN-US"><font face="Times New Roman">n</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">个整数，以空格隔开</span></font></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【输出格式】</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span lang="EN-US"><span style="mso-tab-count: 1"><font face="Times New Roman">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font></span></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">共</span><span lang="EN-US"><font face="Times New Roman">n</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">行，每行输出第</span><span lang="EN-US"><font face="Times New Roman">n</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">步选择时交换哪两个位置的下标，以及交换得到的序列，格式</span><span lang="EN-US"><font face="Times New Roman">:</font></span></font></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[i],a[j]):a[0] &hellip; a[n-1]</font></span></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span lang="EN-US"><font face="Times New Roman">i</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">和</span><span lang="EN-US"><font face="Times New Roman">j</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为所交换元素的下标，下标从</span><span lang="EN-US"><font face="Times New Roman">0</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">开始，最初元素顺序按输入顺序。另外请保证</span><span lang="EN-US"><font face="Times New Roman">i&lt;=j</font></span></font></p>
<p style="text-indent: 21pt; margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span lang="EN-US"><font face="Times New Roman">a[0]&hellip;a[n-1]</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">为交换后的序列，元素间以一个空格隔开</span></font></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【样例输入】</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">5</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">4 3 1 1 2</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【样例输出】</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[0], a[2]):1 3 4 1 2</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[1], a[3]):1 1 4 3 2</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[2], a[4]):1 1 2 3 4</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[3], a[3]):1 1 2 3 4</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">swap(a[4], a[4]):1 1 2 3 4</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'"><font size="3">【数据规模】</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><font size="3" face="Times New Roman">n&lt;=100</font></span></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><font size="3"><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">整数元素在</span><span lang="EN-US"><font face="Times New Roman">int</font></span><span style="font-family: 宋体; mso-ascii-font-family: 'Times New Roman'; mso-hansi-font-family: 'Times New Roman'">范围内</span></font></p>
<p style="margin: 0cm 0cm 0pt" class="MsoNormal"><span lang="EN-US"><o:p><font size="3" face="Times New Roman">&nbsp;</font></o:p></span></p>
<p>&nbsp;</p>